package sortStudy;

import java.util.Arrays;

public class MergeSort {

    public static void main(String[] args) {
        int[] arr = new int[]{
                23, 16, 78, 10, 88, 45, 76, 43, 62, 12, 77, 66
        };
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    //两路归并排序算法
    public static void merge(int[] arr, int[] ans, int low, int m, int high){
        int i, j, k;
        i = low; j = m + 1; k = low;
        while ((i <= m) && j <= high){
            if (arr[i] <= arr[j]){
                ans[k] = arr[i];
                i++;
            } else {
                ans[k] = arr[j];
                j++;
            }
            k++;
        }
        while (i <= m){
            ans[k++] = arr[i++];
        }
        while (j <= high){
            ans[k++] = arr[j++];
        }
    }
    //一趟归并排序算法
    public static void mergePass(int[] arr, int[] ans, int n, int length){
        int i = 0, j;
        while (i + 2*length - 1 < n){
            merge(arr, ans, i, i + length - 1, i + 2*length - 1);
            i += 2*length;
        }
        //如果剩下两个文件
        if (i + length < n){
            merge(arr, ans, i, i+ length - 1, n - 1);
        } else {
            for (j = i; j < n; j++){
                ans[j] = arr[j];
            }
        }
    }
    public static void mergeSort(int[] arr){
        int len = arr.length;
        int[] ans = new int[len];
        int length = 1;
        while (length < len){
            mergePass(arr, ans, len, length);

            length *= 2;

            mergePass(ans, arr, len, length);

            length *= 2;
        }
    }
}
